1. Field of the Invention
This invention relates to a computer in which a virtual storage and a buffer storage are employed, and more particularly, to a buffer storage control apparatus for such a computer.
2. Description of the Related Art
Large-scale and medium-scale computers of recent years usually employ both a virtual storage and a buffer storage. The virtual storage enables a programmer to do coding without regard to the size of a real storage, and provides the programmer with the convenience of addressing a virtual address on a virtual storage rather than a rear address on a real storage. On the other hand, the buffer storage system is a system in which a high-speed and small-capacity buffer storage is located (performance wise) between a central processing unit and a main storage to provide hierarchical storage, in order to supplement a performance gap wherein the main storage is large in capacity but is low in accessing speed in comparison to the operation rate of the central processing unit.
In the virtual storage system, it is necessary to translate a virtual address into a real address before accessing the main storage. This translation is performed by referring to an address translation table in the main storage which is prepared by a program. A time overhead of address translation is large if the program accesses to the main storage at a low speed every time accessing the storage. In order to minimize the number of occurrences of such slow accessing, a translation lookaside buffer (hereinafter called "TLB"), is used as a high speed translation table, wherein translation pairs, i.e., virtual addresses and real addresses, each obtained by accessing the main storage only once, are stored. Before accessing the main storage for a desired translation, first a check is made on whether or not the virtual address to be accessed exists in the TLB. If it exists (this probability is very high due to the locality of reference by a program), a real address can be obtained at a high speed.
In the buffer storage system, since a buffer storage is a copy of part of the main storage, them is provided a buffer address array (hereinafter called "BAA") for storing information representing which part of the main storage the present buffer storage information corresponds to. Before the central processing unit starts accessing the main storage with a virtual address, a check is first made on whether or not the real address translated by the TLB exists in the BAA. If it exists (this probability is also very high due to the locality of reference), a slow speed accessing of the main storage can be avoided, with the data being read instead from the buffer storage at high speed and then transferred to the central processing unit.
In the foregoing description, accessing of the TLB and BAA are performed serially. However the foregoing approach is disadvantageous in terms of time, and in order to improve a time performance, it is necessary to reference the TLB and BAA in parallel for high-speed processing. In that case, the BAA is referred to with the virtual address. More exactly, the BAA is referred to with a real address portion (in-page address) in the virtual address, which is a lower part of the virtual address which is unchanged even after the virtual-to-real address translation. In general, since data of the main storage is associated with data of the buffer storage by 32 bytes or 64 bytes (called a block), the number of bits usable when accessing the BAA is 6 or 7 at most.
FIG. 4 of the accompanying drawings is a block diagram showing one example of a buffer storage system in which the TLB and BAA are accessed in parallel. A memory access request created in the central processing unit stores a virtual address in a register 1. An entry of a TLB 2 is accessed by the lower bits of a page address of the virtual address. In this example, the TLB 2 is composed of k columns.times.2 rows, wherein 2-1 and 2-2 designate first and second rows, respectively. Namely, there are k entries in each of the first and second rows. Each entry of each of the first and second rows 2-1, 2-2 of the TLB 2 is composed of a virtual address (L) portion, a valid flag bit (V) portion, and a real address (R) portion. The contents of the L and V portions read from each row of the TLB 2 are compared with upper bits of a page address in the register 1 using corresponding virtual address comparator circuits 4-1, 4-2.
On the other hand, a BAA 3 is accessed by the upper bits of the page address. In this example, the BAA 3 is composed of l columns.times.2 rows, wherein 3-1 and 3-2 designate the first and second rows, respectively. Namely, each of the first and second rows has l entries. In the described system which references TLB 2 and BAA 3 in parallel, the number of columns l of the BAA 3 is determined according to a block size is 4 KB (kilo bytes) and block size is 64 B (bytes), l=64 columns. The number of rows is determined according to the buffer memory capacity. Each entry of the BAA 3 is composed of a real address (R) portion and a valid flag bit (V) portion. Real address comparator circuits 6-1, 6-2 compare A.) a real address (page address) read from the R portion of the second row 2-1 of the TLB, or, B.) the real address (page address) stored in a register 1 by the central processing unit (both A. and B. being inputted via a selecting circuit), with the contents read from the corresponding R portions of the BAA rows 3-1, 3-2. The selecting circuit 5 selects the content of the register 1 if a real address is stored in the register 1 directly by the central processing unit, and selects the content of the first row 2-1 of the TLB if a virtual address is stored in the register 1. Other real address comparator circuits 7-1, 7-2 compare the real address read from the R portion of the second row 2-2 of the TLB with the corresponding real addresses read from the R portions of the first and second rows 3-1, 3-2 of the BAA. When the two inputs of each real address comparator circuit 6-1, 6-2, 7-1, 7-2 coincide with each other, its output will be "1".
The results of comparison by the real address comparator circuits 6-1, 6-2, 7-1, 7-2 are inputted to an encoder 8 and are selected according to the results of the virtual address comparator circuits 4-1, 4-2, and, thereafter, the encoded output (one bit in this example) is stored in an upper bit of a register 9. In the lower order bit positions of the register 9, an in-page address of the register 1 is stored. Thus a buffer storage address corresponding to a virtual address (or real address) stored in the register 1 is obtained in the register 9. The buffer storage is indexed by the address in the register 9, and the read data is transferred to the central processing unit.
As ultra LSIs (Large Scale Integrated Circuits) have recently been developed and improved, the realization of large-scale and high-speed computers are on the rise. Presumably this tendency will continue into the future. As a result of this increased integration, many logical units such as operational units are formed on a large scale integrated circuit for high-speed processing. Gates for distribution of address to memories and for collection of data read from memories occupy a majority of logical portions associated with the memories, and such components make the formation of an LSI difficult and are highly likely to become a critical constraint on minimization of a machine cycle of a computer. Further, the capacity of main storage also tends to be increased, and, as a result thereof, the capacity of the buffer storage is also required to be increased, namely, the capacity of the BAA is required to be increased. Large scale integration of memories has advanced a sufficient degree so that high-speed memories can be realized. Regarding the BAA, only 6 or 7 bits at most can be permitted for the number of columns in the system in which the TLB and BAA are accessed in parallel, while the large scale integration of memories results in an increase in the number of bits of a word. Consequently, a large-capacity BAA using conventional memories such as that of FIG. 6 is difficult to achieve due to a sharp increase in the number of package pins of the memories.
Assuming that a memory of 4K bits is composed of 64 words, such a memory can contain 64 bits per word and a resulting requirement for both address and data lines would reach 140 pins. In implementation of memory LSI components, a package size of the memory is limited by the number of input and output pins.
Japanese Patent Publication No. 57-57784 (Japanese Patent Laid-Open Publication No. 54-102930) discloses an apparatus in which TLB and BAA are composed of memories each having comparator circuits built therein. For example, the portions surrounded by dashed lines in FIG. 4 are built in a memory chip.
However, in this prior art, the real address translation read from the TLB is required to be outputted from the memory chip constituting the TLB, is then inputted to a memory chip constituting the BAA and is compared with real addresses within the BAA. Therefore, two disadvantages are encountered in that there is a propagation delay and the number of pins needed for input and output of the TLB and BAA is increased.
A solution has been proposed by Japanese Patent Laid-Open Publication No. 62-101944. This storage control apparatus comprises a first portion of a TLB, a second memory for holding a real address portion of a BAA, comparator circuits for comparing the output of the first memory with the output of the second memory, with all such arrangements being built in a memory device. The first and second memories are connected to different address signal inputs, and connected to a common dam-in signal input. This storage control apparatus is shown in FIG. 5. Like reference numerals designate similar parts or elements throughout FIGS. 4 and 5. A portion surrounded by a dashed line in FIG. 5 is a memory device chip disclosed in the Japanese Publication No.62-101944. This memory chip includes parts corresponding to the rows 3-1, 3-2 of BAA 3 and the comparator circuits 6-1, 6-2, 7-1, 7-2, which constitute the BAA 3 the R portions 2-13, 2-23 of each row which constitute the TLB 2, and the selecting circuit 5, all parts being built in the memory chip. Each row 3-1, 3-2 of the BAA is connected to a common input to be a column address, i.e., namely, to the upper bits of a page address of the address register 1. Each R portion 2-13, 2-23 of the TLB is connected to a common input to be a column address different from that of the BAA, i.e., namely, to the lower bits of a page address of the address register 1. Each row 3-1, 3-2 of the BAA and each R portion 2-13, 2-23 of the TLB are connected to a common dam-in signal input, namely, to a page address of the address register 1. With this arrangement, the real address read from the TLB can be compared with the real address read from the BAA, without any outputting/inputting of such read addresses with respect to external pins of the memory chip. The V portion of the BAA, like the R portion, may be inputted to the comparator circuits. Also the L portion, the V portion and the comparator circuits 4-1, 4-2 of the TLB may be formed as a memory chip with built-in comparator circuits.
FIG. 6 is a block diagram showing another storage control apparatus which is disclosed in Japanese Patent Laid-Open Publication No. 62-101944. In this apparatus, unlike the apparatus of FIG. 5, two memory devices are used. In FIG. 5, the number of rows of the BAA is 2. If the number of rows is more t n 2, it is often difficult to contain the elements in a single memory device. The example of FIG. 6 is particularly useful in such case. Either the memory device 100 or the memory device 101 has a construction identical with that of the memory device of FIG. 5. The R portions of 2-13, 2-13' of the memory devices 100, 101 are the R portion of the first row of the TLB, in which identical real addresses are stored. Further, the R portions 2-23, 2-23' of the memory devices 100, 101 are the R portion of the second row of the TLB, in which identical real addresses are stored. Further, 3-1 and 3-2 of the memory device 100 are the first and second rows, respectively, of the BAA. Finally, 3-3 and 3-4 of the memory device 101 are the third and fourth rows, respectively, of the BAA.
Thus,by increasing the number of memory devices with respect to an increase of the number of rows of the BAA and by forming such in the respective memory devices the R portions constituting the same row of the TLB (similar to the example of FIG. 5), the real address read from the TLB can be compared with the R portion of the BAA, without requiring outputting/inputting of read real addresses from one chip to another.
In Japanese Patent Publication No. 57-57784 and Japanese Patent Laid-Open Publication No. 62-101944, assuming that the TLB includes m rows, the BAA includes n rows (practically, the TLB has two rows, while the BAA has two rows in FIGS. 4 and 5 and four rows in FIG. 6), m comparator circuits for real addresses of the TLB and BAA are needed per row of the BAA (m.times.n in total), and n RAMs are needed for the BAA.
Therefore, if the TLB has two rows and the BAA has four rows, two comparator circuits per row of the BAA, namely, eight comparator circuits in total are needed. FIG. 2 is a layout diagram showing the case in which these elements are realized using a single memory device (LSI).
In FIG. 2, a data line 2-1 of the real address portion RO (2-13) of the row 0, which is the first row of the TLB, is connected to comparator circuits COO to C03 (6-1 to 6-4) and is thereby compared with each read data of the four rows BO to B3 (3-1 to 3-4) of the BAA. Likewise, a data line 20-2 of the real address portion R1 (2-23) of the row 1, which is the second row of the TLB, is connected to comparator circuits C10 to C13 (7-1 to 7-4) and is thereby compared with each read data of the four rows BO to B3 of the BAA. 300 and 301 in FIG. 2 designate repeat units (hereinafter called "macro cells") constituting a memory device with comparator circuits, the layouts of the macro cells 300, 301 being identical with each other. Even if the macro cells 300, 301 are located on a common chip, it is preferable that such macro cells be designed in a compact form and repeated across the common chip to reduce the number of layout designing steps of an LSI. In the prior art of FIG. 2, the real address portion of the TLB has a number of columns two times larger than the number of columns of the BAA by using RAMs equivalent to two RAMs of the BAA. Since the macro cells 300, 301 are the same units, the macro cell 300 including the real address portion of the TLB also includes comparators 10, 11, although they are not used.
In the prior art of FIG. 2, since one set of comparator circuits (COO to C03 or C 10 to C13) corresponding to each row of the TLB is extended in one direction (horizontally in the drawing), the data lines 20-1, 20-2 leading from the real address portions of the TLB to the comparator circuits of the BAA are required to be long, and also, intersection of the lines is caused.
To shorten the data lines 20-1, 20-2 leading from the TLB to the comparators, the comparator circuits COO to C03 associated with the row 0 of the TLB may be located on the left side, and the comparator circuits C10 to C13 associated with the row 1 of the TLB may be located on the right side, as shown in FIG. 3.
In the case of FIG. 3, instead of reducing the length of the data lines 20-1, 20-2, the data lines 30-1 to 30-4 leading from the BAA to the comparator circuits are elongated as compared to the case of FIG. 2, and still cause an intersection of the data lines. This intersection and elongation of the data lines chiefly increases sparasitic capacitances associated therewith and hence causes an increase in signal delay due to the non-ideal layout of the data lines. The signal delay due to the data lines has increased in ratio to the total delay time as a working speed of modem gate devices or other elements has increased. As a further disadvantage of the non-ideal layout, the area required for wiring the datelines is increased so that the required size of the resultant chip is enlarged.